package offerbook.Code25_pathInBT;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 *
 * 找出路径和等于给定数值的路径总数。
 *
 * 路径不需要从根节点开始，也不需要在叶子节点结束，
 * 但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 *
 * 示例：
 *
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 *
 *       10
 *      /  \
 *     5   -3
 *    / \    \
 *   3   2   11
 *  / \   \
 * 3  -2   1
 *
 * 返回 3。和等于 8 的路径有:
 *
 * 1.  5 -> 3
 * 2.  5 -> 2 -> 1
 * 3.  -3 -> 11
 * @date 2020/3/9 19:17
 */
public class Code06_FindSumInAllPath4_leetcode437 {
    /**
     * 方式1：先序遍历，以每个节点开始往下找。
     * <p>
     * 时间复杂度O(n²)
     */
    public static int pathSum1(TreeNode treeNode, int sum){
        List<Integer> res = new LinkedList<>();
        res.add(0);
        process1(treeNode,sum,res);
        return res.get(0);
    }
    private static void process1(TreeNode root, int sum, List<Integer> res) {
        if (root == null) return;
        //对每个节点作为根节点进行递归
        preOrder(root, sum,res);
        process1(root.left, sum, res);
        process1(root.right, sum, res);
    }

    private static void preOrder(TreeNode temp, int sum, List<Integer> res) {
        if (temp == null) return;
        sum -= temp.val;
        if (sum == 0) {
            int count = res.get(0);
            res.set(0,count+1);
            //这里return可以不写，写了提前剪枝。另外写了会影响正负相互抵消
//            return;
        }
        preOrder(temp.left, sum, res);
        preOrder(temp.right, sum, res);
    }


    /**
     * 方式2：以当前节点为终止节点的思路
     /对树的先序遍历中，设定一个数组，数组存放的是遍历的路径的值。
     * <p>
     * 当来到节点node，从node开始向上遍历数组，查询所有可能以node为终点的满足sum的路径和。
     * <p>
     * 数组长度最多是logn。时间复杂度是O(nlogn)。
     */
    public  int pathSum2(TreeNode treeNode, int sum) {
        if(treeNode == null) return 0;
        int[]path = new int[1000];

        return  process2(treeNode,sum,path,0);
    }

    private static int process2(TreeNode root, int sum, int[] path/*保存路径*/, int index/*指向路径终点*/) {
        if (root == null) return 0;
        path[index] = root.val;
        int n = 0;
        int temp = 0;
        //从当前节点往父节点找路径
        //数组长度最大是logn
        for (int i = index; i >= 0; i--) {
            if ((temp += path[i]) == sum) n++;
        }
        int left = process2(root.left, sum, path, index + 1);
        int right = process2(root.right, sum, path, index + 1);
        return n + left + right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.left.left = new TreeNode(5);
        root.right.left.right = new TreeNode(1);
        root.right.right = new TreeNode(4);
        TreeUtil.printTree(root);
        int sum = pathSum1(root,22);
        System.out.println(sum);
    }

}
